package com.code.answer;

import com.code.ListNode;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;

/**
*@author Ysl
*@create 2025/7/2 15:47
*/
public class Test {


    public static void main(String[] args) {

       int []num = {1,3,6,9};
        System.out.println(lengthOfLastWord("  fly me   to   the moon  "));

    }

    public static int lengthOfLastWord(String s) {

        while (s.endsWith(" ")){
            s = s.substring(0, s.length()-1);
        }

        int count = 0;
        char[] charArray = s.toCharArray();
        for (int i = charArray.length-1; i >= 0; i--) {
            if (charArray[i] == ' '){
                break;
            }
            count++;
        }
        return count;
    }

    public static int searchInsert(int[] nums, int target) {
        int n = nums.length;
        if (nums.length == 0){
            return 0;
        } else {
            if (nums[0] > target){
                return 0;
            }
        }
        if (nums[n-1] < target){
            return n;
        }
        

        int l = 0;
        int r = nums.length - 1;

        while (l <= r){
            int mid = (l + r) / 2;
            if (nums[mid] == target){
                return mid;
            } else if (nums[mid] < target){
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    public static int strStr(String haystack, String needle) {
        int indexOf = haystack.indexOf(needle);
        return indexOf;
    }

    public static int removeDuplicates(int[] nums) {
        Set<Integer> list = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            list.add(nums[i]);
        }
        return list.size();
    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.getVal() < l2.getVal()) {
             l1.setNext(mergeTwoLists(l1.getNext(), l2));
            return l1;
        } else {
            l2.setNext(mergeTwoLists(l1, l2.getNext()));
            return l2;
        }

    }


    public static int threeSumClosest(int[] nums, int target) {

        return target;
    }

    /**
     * 15. 三数之和
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> res = new ArrayList<>();
        nums = Arrays.stream(nums).sorted().toArray();
        System.out.println(Arrays.toString(nums));


        for (int i = 0; i < nums.length; i++){
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            if (nums[i] > 0){
                return res;
            }
            int tag = -nums[i];
            int j = i + 1, k = nums.length - 1;
            while (j < k){
                int sum = nums[j] + nums[k];
                if (sum == tag){
                    res.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    while (j < k && nums[j] == nums[j + 1]) {
                        j++; // 跳过重复的 nums[j]
                    }
                    while (j < k && nums[k] == nums[k - 1]) {
                        k--; // 跳过重复的 nums[k]
                    }
                    j++;
                    k--;
                } else if (sum < tag){
                    j++;
                } else {
                    k--;
                }
            }
        }

        return res;
    }

    /**
     * 14. 最长公共前缀
     * @param strs
     * @return
     */
    public static String longestCommonPrefix(String[] strs) {
        String prefix = strs[0];

        for (int i = 1; i < strs.length; i++) {
            while (!strs[i].startsWith(prefix)){
                prefix = prefix.substring(0, prefix.length() - 1);
            }
        }
        return prefix;
    }

    /**
     * 13.罗马数字转整数
     * @param s
     * @return
     */
    public static int romanToInt(String s) {
        String[] thousands = {"", "M", "MM", "MMM"};
        String[] hundreds  = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
        String[] tens      = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
        String[] ones      = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};

        int num = 0;
        for (int i = thousands.length-1; i >0 ; i--) {
            if (s.indexOf(thousands[i]) == 0){
                num = num + i*1000;
                s = s.substring(thousands[i].length());
                break;
            }
        }

        for (int i = hundreds.length-1; i >0 ; i--) {
            if (s.indexOf(hundreds[i]) == 0){
                num = num + i*100;
                s = s.substring(hundreds[i].length());
                break;
            }
        }

        for (int i = tens.length-1; i >0 ; i--) {
            if (s.indexOf(tens[i]) == 0){
                num = num + i*10;
                s = s.substring(tens[i].length());
                break;
            }
        }


        for (int i = ones.length-1; i >0 ; i--) {
            if (s.indexOf(ones[i]) == 0){
                num = num + i;
                s = s.substring(tens[i].length());
                break;
            }
        }


        return num;
    }

    /**
     * 13.罗马数字转整数
     * 更优化
     * @param s
     * @return
     */
    public static int intToRoman2(String s) {
        int sum=0;
        int preNum=getValue(s.charAt(0));
        for(int i=1;i<s.length();i++){
            int num=getValue(s.charAt(i));
            if(preNum<num){
                sum-=preNum;
            }else{
                sum+=preNum;
            }
            preNum=num;
        }
        sum+=preNum;
        return sum;
    }

    private static int getValue(char ch) {
        switch(ch) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
            default: return 0;
        }
    }

    /**
     * 12 整数转罗马数字
     * @param num
     * @return
     */
    public String intToRoman(int num) {

        String[] thousands = {"", "M", "MM", "MMM"};
        String[] hundreds  = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
        String[] tens      = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
        String[] ones      = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};

        StringBuffer roman = new StringBuffer();
        roman.append(thousands[num / 1000]);
        roman.append(hundreds[num % 1000 / 100]);
        roman.append(tens[num % 100 / 10]);
        roman.append(ones[num % 10]);
        return roman.toString();


    }

    /**
     * 11.盛最多水的容器
     * 暴力双循环
     * @param height
     * @return
     */
    public static int maxArea(int[] height) {
        int num = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = i + 1; j < height.length; j++){
                int area = Math.min(height[i], height[j]) * (j - i);
                num = Math.max(num, area);
            }
        }

        return num;
    }

    /**
     * 11.盛最多水的容器
     * 双指针
     * @param height
     * @return
     */
    public static int maxArea2(int[] height) {
        int num = 0;
        int left = 0;
        int right = height.length - 1;
        while (left < right) {
            int area = Math.min(height[left], height[right]) * (right - left);
            num = Math.max(num, area);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return num;
    }

    /**
     * 9.回文数
     * @param x
     * @return
     */
    public static boolean isPalindrome(int x) {
        if (x < 0){
            return false;
        }
        String string = String.valueOf(x);
        char[] charArray = string.toCharArray();
        for (int i = 0; i < charArray.length; i++) {
            if (charArray[i] != string.charAt(string.length() - i - 1)){
                return false;
            }
        }
        return true;
    }

    /**
     * 9.回文数
     * 双指针法
     * @param x
     * @return
     */
    public static boolean isPalindrome2(int x) {
        if (x < 0) {
            return false;
        }
        String s = String.valueOf(x);
        int left = 0;
        int right = s.length() - 1;

        // 双指针比较
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;

    }

    /**
     * 9.回文数
     * 数字反转法
     * @param x
     * @return
     */
    public static boolean isPalindrome3(int x) {
        // 负数直接返回 false
        if (x < 0) {
            return false;
        }
        // 0 或个位数直接返回 true
        if (x < 10) {
            return true;
        }

        int original = x;
        int reversed = 0;

        // 反转数字
        while (x > 0) {
            reversed = reversed * 10 + x % 10;
            x /= 10;
        }

        return original == reversed;
    }

    /**
     * 1.两数之和
     * 56ms
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++){
            for (int j = i + 1; j < nums.length; j++){
                if (nums[i] + nums[j] == target){
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }

    /**
     * 1.两数之和
     * 2ms
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum2(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey( complement)){
                return new int[]{map.get(complement), i};
            }
            map.put(nums[i], i);
        }
        return new int[]{};
    }

    /**
     * 2.两数相加
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return addTwoNumbers(l1, l2, 0);
    }

    private static ListNode addTwoNumbers(ListNode l1, ListNode l2, int carry) {
        if (l1 == null && l2 == null && carry == 0) {
            return null;
        }

        int sum = carry;
        if (l1 != null) {
            sum += l1.getVal();
            l1 = l1.getNext();
        }
        if (l2 != null) {
            sum += l2.getVal();
            l2 = l2.getNext();
        }

        ListNode result = new ListNode(sum % 10);
        result.setNext(addTwoNumbers(l1, l2, sum / 10));
        return result;
    }

    /**
     * 5.最长回文子串
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }

        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            // 奇数长度（如 "bab"）
            int len1 = expandAroundCenter(s, i, i);
            // 偶数长度（如 "baab"）
            int len2 = expandAroundCenter(s, i, i + 1);
            int maxLen = Math.max(len1, len2);

            // 更新最长回文子串开始及结束位置
            if (maxLen > end - start) {
                start = i - (maxLen - 1) / 2;
                end = i + maxLen / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    /**
     * 获取回文子串的长度
     * @param s
     * @param left
     * @param right
     * @return
     */
    private static int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        // 返回回文长度
        return right - left - 1;
    }

    /**
     * 6.Z 字形变换
     * @param str
     * @param num
     * @return
     */
    public static String convert(String str, int num) {
        if (num == 1){
            return str;
        }

        StringBuilder[] builders = new StringBuilder[num];
        for (int i = 0; i < num; i++) {
            builders[i] = new StringBuilder();
        }
        int index = 0;
        int step = 1;
        for (int i = 0; i < str.length(); i++) {
            builders[index].append(str.charAt(i));
            // 更新下一个索引
            index += step;
            if (index == num-1 || index == 0){
                step *= -1;
            }
        }

        StringBuilder result = new StringBuilder();
        for (StringBuilder sb : builders) {
            result.append(sb);
        }
        return result.toString();
    }

    /**
     * 7.整数反转
     * @param x
     * @return
     */
    public static int reverse(int x) {

        boolean flag = true;
        if (x == Integer.MIN_VALUE ){
            return 0;
        } else if (x < 0){
            x = -x;
            flag = false;
        }

        String s = String.valueOf(x);
        StringBuilder builder = new StringBuilder();
        for (int i = s.length() - 1; i >= 0; i--) {
            builder.append(s.charAt(i));
        }

        long i = flag ? Long.parseLong(builder.toString()) : -Long.parseLong(builder.toString());
        if (i > Integer.MAX_VALUE){
            return 0;
        } else if (i < Integer.MIN_VALUE){
            return 0;
        }

        return (int) i;

    }

    /**
     * 8.字符串转换整数
     * @param s
     * @return
     */
    public static int  myAtoi(String s) {

        s = s.trim();
        System.out.println( s);

        char[] charArray = s.toCharArray();

        int index = 0;
        StringBuilder builder = new StringBuilder();
        boolean flag = true;

        while (index < charArray.length){
            int q = index +1;
            boolean f = q<charArray.length && Character.isDigit(s.charAt(q));

            if (index == charArray.length-1 && Character.isDigit(s.charAt(index))){
                builder.append(charArray[ index]);
            } else if (Character.isDigit(s.charAt(index)) && f) {
                builder.append(charArray[ index]);

            } else {
                if (index > 0 && !Character.isDigit(s.charAt(index))){
                    break;
                }
                if (charArray[index] == '+' || charArray[index] == '-'){
                    if (charArray[index] == '-'){
                        flag = false;
                    }
                } else if (!Character.isDigit(s.charAt(index))){
                    break;
                } else {
                    builder.append(charArray[ index]);
                }

            }
            index++;

        }

        if (builder.length() >0){
            boolean negative = flag;
            int result = 0;
            int i = 0, len = builder.length();

            // 遍历字符并计算
            while (i < len) {
                char c = builder.charAt(i);
                if (c < '0' || c > '9') {
                    throw new NumberFormatException("非法字符: " + c);
                }
                int digit = c - '0';

                // 检查是否溢出
                if (result > (Integer.MAX_VALUE - digit) / 10) {
                    return negative ?  Integer.MAX_VALUE :Integer.MIN_VALUE ;
                }
                result = result * 10 + digit;
                i++;
            }

            return negative ? result : -result;
        } else {
            return 0;
        }
    }

    /**
     * leetcode 8
     * 字符串转换整数
     * @param s
     * @return
     */
    public static int  myAtoi2(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }

        // 去除前导空格
        s = s.trim();
        if (s.isEmpty()) {
            return 0;
        }

        int index = 0;
        int sign = 1; // 1 表示正数，-1 表示负数
        int result = 0;

        // 处理正负号
        if (s.charAt(index) == '+' || s.charAt(index) == '-') {
            sign = s.charAt(index) == '-' ? -1 : 1;
            index++;
        }

        // 遍历数字字符
        while (index < s.length() && Character.isDigit(s.charAt(index))) {
            int digit = s.charAt(index) - '0';

            // 检查溢出
            if (result > (Integer.MAX_VALUE - digit) / 10) {
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }

            result = result * 10 + digit;
            index++;
        }

        return sign * result;
    }
}
